<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Hard
  </div>
  <div>
   <h1 class="question_title">
    781. Basic Calculator IV
   </h1>
   <p>
    Given an
    <code>
     expression
    </code>
    &nbsp;such as
    <code>
     expression = "e + 8 - a + 5"
    </code>
    and an evaluation map such as
    <code>
     {"e": 1}
    </code>
    (given in terms of
    <code>
     evalvars = ["e"]
    </code>
    and
    <code>
     evalints = [1]
    </code>
    ), return a list of tokens representing the simplified expression, such as
    <code>
     ["-1*a","14"]
    </code>
   </p>
   <ul>
    <li>
     An expression alternates chunks and symbols, with a space separating each chunk and symbol.
    </li>
    <li>
     A chunk is either an expression in parentheses, a variable, or a non-negative integer.
    </li>
    <li>
     A variable is a string of lowercase letters (not including digits.) Note that variables can be multiple letters, and note that variables never have a leading coefficient or unary operator like
     <code>
      "2x"
     </code>
     or
     <code>
      "-x"
     </code>
     .
    </li>
   </ul>
   <p>
    Expressions are evaluated in the usual order: brackets first, then multiplication, then addition and subtraction. For example,
    <code>
     expression = "1 + 2 * 3"
    </code>
    has an answer of
    <code>
     ["7"]
    </code>
    .
   </p>
   <p>
    The format of the output is as follows:
   </p>
   <ul>
    <li>
     For each term of free variables with non-zero coefficient, we write the free variables within a term in sorted order lexicographically. For example, we would never write a term like
     <code>
      "b*a*c"
     </code>
     , only
     <code>
      "a*b*c"
     </code>
     .
    </li>
    <li>
     Terms have degree equal to the number of free variables being multiplied, counting multiplicity. (For example,
     <code>
      "a*a*b*c"
     </code>
     has degree 4.) We write the largest degree terms of our answer first, breaking ties by lexicographic order ignoring the leading coefficient of the term.
    </li>
    <li>
     The leading coefficient of the term is placed directly to the left with an asterisk separating it from the variables (if they exist.)&nbsp; A leading coefficient of 1 is still printed.
    </li>
    <li>
     An example of a well formatted answer is
     <code>
      ["-2*a*a*a", "3*a*a*b", "3*b*b", "4*a", "5*c", "-6"]
     </code>
     &nbsp;
    </li>
    <li>
     Terms (including constant terms) with coefficient 0 are not included.&nbsp; For example, an expression of "0" has an output of [].
    </li>
   </ul>
   <p>
    <strong>
     Examples:
    </strong>
   </p>
   <pre>
<strong>Input:</strong> expression = "e + 8 - a + 5", evalvars = ["e"], evalints = [1]
<strong>Output:</strong> ["-1*a","14"]

<strong>Input:</strong> expression = "e - 8 + temperature - pressure",
evalvars = ["e", "temperature"], evalints = [1, 12]
<strong>Output:</strong> ["-1*pressure","5"]

<strong>Input:</strong> expression = "(e + 8) * (e - 8)", evalvars = [], evalints = []
<strong>Output:</strong> ["1*e*e","-64"]

<strong>Input:</strong> expression = "7 - 7", evalvars = [], evalints = []
<strong>Output:</strong> []

<strong>Input:</strong> expression = "a * b * c + b * a * c * 4", evalvars = [], evalints = []
<strong>Output:</strong> ["5*a*b*c"]

<strong>Input:</strong> expression = "((a - b) * (b - c) + (c - a)) * ((a - b) + (b - c) * (c - a))",
evalvars = [], evalints = []
<strong>Output:</strong> ["-1*a*a*b*b","2*a*a*b*c","-1*a*a*c*c","1*a*b*b*b","-1*a*b*b*c","-1*a*b*c*c","1*a*c*c*c","-1*b*b*b*c","2*b*b*c*c","-1*b*c*c*c","2*a*a*b","-2*a*a*c","-2*a*b*b","2*a*c*c","1*b*b*b","-1*b*b*c","1*b*c*c","-1*c*c*c","-1*a*a","1*a*b","1*a*c","-1*b*c"]
</pre>
   <p>
    <strong>
     Note:
    </strong>
   </p>
   <ol>
    <li>
     <code>
      expression
     </code>
     will have length in range
     <code>
      [1, 250]
     </code>
     .
    </li>
    <li>
     <code>
      evalvars, evalints
     </code>
     will have equal lengths in range
     <code>
      [0, 100]
     </code>
     .
    </li>
   </ol>
  </div>
  <div>
   <h1 class="question_title">
    781. 基本计算器 IV
   </h1>
   <p>
    给定一个表达式&nbsp;
    <code>
     expression
    </code>
    &nbsp;如&nbsp;
    <code>
     expression = "e + 8 - a + 5"
    </code>
    &nbsp;和一个求值映射，如&nbsp;
    <code>
     {"e": 1}
    </code>
    （给定的形式为&nbsp;
    <code>
     evalvars = ["e"]
    </code>
    和&nbsp;
    <code>
     evalints = [1]
    </code>
    ），返回表示简化表达式的标记列表，例如
    <code>
     ["-1*a","14"]
    </code>
   </p>
   <ul>
    <li>
     表达式交替使用块和符号，每个块和符号之间有一个空格。
    </li>
    <li>
     块要么是括号中的表达式，要么是变量，要么是非负整数。
    </li>
    <li>
     块是括号中的表达式，变量或非负整数。
    </li>
    <li>
     变量是一个由小写字母组成的字符串（不包括数字）。请注意，变量可以是多个字母，并注意变量从不具有像&nbsp;
     <code>
      "2x"
     </code>
     &nbsp;或&nbsp;
     <code>
      "-x"
     </code>
     &nbsp;这样的前导系数或一元运算符&nbsp;。
    </li>
   </ul>
   <p>
    表达式按通常顺序进行求值：先是括号，然后求乘法，再计算加法和减法。例如，
    <code>
     expression = "1 + 2 * 3"
    </code>
    &nbsp;的答案是
    <code>
     ["7"]
    </code>
    。
   </p>
   <p>
    输出格式如下：
   </p>
   <ul>
    <li>
     对于系数非零的每个自变量项，我们按字典排序的顺序将自变量写在一个项中。例如，我们永远不会写像
     <code>
      &ldquo;b*a*c&rdquo;
     </code>
     这样的项，只写
     <code>
      &ldquo;a*b*c&rdquo;
     </code>
     。
    </li>
    <li>
     项的次数等于被乘的自变量的数目，并计算重复项。(例如，
     <code>
      "a*a*b*c"
     </code>
     的次数为 4。)。我们先写出答案的最大次数项，用字典顺序打破关系，此时忽略词的前导系数。
    </li>
    <li>
     项的前导系数直接放在左边，用星号将它与变量分隔开(如果存在的话)。前导系数 1 仍然要打印出来。
    </li>
    <li>
     格式良好的一个示例答案是&nbsp;
     <code>
      ["-2*a*a*a", "3*a*a*b", "3*b*b", "4*a", "5*c", "-6"]
     </code>
     &nbsp;。
    </li>
    <li>
     系数为 0 的项（包括常数项）不包括在内。例如，&ldquo;0&rdquo; 的表达式输出为 []。
    </li>
   </ul>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     示例：
    </strong>
   </p>
   <pre><strong>输入：</strong>expression = "e + 8 - a + 5", evalvars = ["e"], evalints = [1]
<strong>输出：</strong>["-1*a","14"]

<strong>输入：</strong>expression = "e - 8 + temperature - pressure",
evalvars = ["e", "temperature"], evalints = [1, 12]
<strong>输出：</strong>["-1*pressure","5"]

<strong>输入：</strong>expression = "(e + 8) * (e - 8)", evalvars = [], evalints = []
<strong>输出：</strong>["1*e*e","-64"]

<strong>输入：</strong>expression = "7 - 7", evalvars = [], evalints = []
<strong>输出：</strong>[]

<strong>输入：</strong>expression = "a * b * c + b * a * c * 4", evalvars = [], evalints = []
<strong>输出：</strong>["5*a*b*c"]

<strong>输入：</strong>expression = "((a - b) * (b - c) + (c - a)) * ((a - b) + (b - c) * (c - a))",
evalvars = [], evalints = []
<strong>输出：</strong>["-1*a*a*b*b","2*a*a*b*c","-1*a*a*c*c","1*a*b*b*b","-1*a*b*b*c","-1*a*b*c*c","1*a*c*c*c","-1*b*b*b*c","2*b*b*c*c","-1*b*c*c*c","2*a*a*b","-2*a*a*c","-2*a*b*b","2*a*c*c","1*b*b*b","-1*b*b*c","1*b*c*c","-1*c*c*c","-1*a*a","1*a*b","1*a*c","-1*b*c"]
</pre>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     提示：
    </strong>
   </p>
   <ol>
    <li>
     <code>
      expression
     </code>
     的长度在&nbsp;
     <code>
      [1, 250]
     </code>
     &nbsp;范围内。
    </li>
    <li>
     <code>
      evalvars, evalints
     </code>
     在范围&nbsp;
     <code>
      [0, 100]
     </code>
     &nbsp;内，且长度相同。
    </li>
   </ol>
  </div>
 </body>
</html>